#include "general_my.h"
#include "loadTestCase.h"

typedef struct AnswerSeq
{
    int * seq;
    struct AnswerSeq * next;
} AnswerSeq;

typedef struct AnswerChain
{
    int answer_num;
    AnswerSeq * head;
    AnswerSeq * tail;
    AnswerSeq * temp;
} AnswerChain;

AnswerChain * createChain();

AnswerSeq * createSeq(int * seq);

AnswerChain * appendSeq(AnswerChain * chain, AnswerSeq * seq);




AnswerChain * doOriginalSimple(CasePair * pair){
    // == 要获得所有的解，必须要暴力搜索解空间，复杂度 O(2^N)，每个物体都有取和不取两种可能
    // == 或者先分组，将相等的
    // * 用一个栈处理即可，如果后面有小于剩余空间的物体，则物体入栈
    // * 如果找不到，弹出当前的元素
    // * 如果背包空间恰好为0，则找到一个样例，记录下栈当前的状态以及该物体插入Answer末尾

    AnswerChain * answer_chain = (AnswerChain *) createChain();

    int backpack_volume = pair->backpack_volume;
    int item_num = *(pair->item_weights) - 1;
    int * item_weights = pair->item_weights + 1;

    int stack_pointer = 0;
    // * 加一位避免溢出
    int * stack = (int *) malloc(sizeof(int) * item_num + 1);
    memset(stack, -1, item_num);

    int left_volume = backpack_volume;
    // * i 相当于栈底指针，永远指向栈底元素
    for (int i=0; i<item_num; i++){
        // * 栈底指针每移动一次，重置剩余空间、栈顶指针、栈
        stack_pointer = 0;
        left_volume = backpack_volume;
        memset(stack, -1, item_num);

        // * 每次先把栈底元素入栈，如果小于就入栈，等于就刚好是一个解答，大于则直接后面都不是
        if (left_volume < item_weights[i]){
            stack[stack_pointer++] =  item_weights[i];
            left_volume -= item_weights[i]; 
        }
        else if (left_volume == item_weights[i]){
            stack[stack_pointer++] = item_weights[i];
            left_volume -= item_weights[i];
            answer_chain = appendSeq(answer_chain, createSeq(stack));
            continue;
        }
        else
            continue;

        // for (int j=)
        // if (*(item_weights + i) = )
    }
}


int main(void){
    CaseSuite * suite = (CaseSuite *) initTestSuite("../test_file_no_value.txt", ' ', true);

    // AnswerChain * chain =   createChain();
    // AnswerSeq * seq = createSeq((int []){1,2,3, -1});
    // chain = appendSeq(chain, seq);
    // printf("done\n");
    CasePair * pair_to_solve = suite->head->nextCase;
    for (int i=0; i< suite->length; i++){
        doOriginalSimple(pair_to_solve);
        pair_to_solve = pair_to_solve->nextCase;
    }
    return 0;
}



AnswerChain * createChain(){
    AnswerChain * chain = (AnswerChain *) malloc(sizeof(AnswerChain));
    if (NULL == chain)
        exit(-1);
    
    AnswerSeq * head = (AnswerSeq *) malloc(sizeof(AnswerSeq));
    if (NULL == head)
        exit(-1);

    AnswerSeq * tail = (AnswerSeq *) malloc(sizeof(AnswerSeq));
    if (NULL == tail)
        exit(-1);

    chain->head = head;
    chain->tail = tail;
    chain->answer_num = 0;
    chain->temp = chain->head;
    chain->temp->next = chain->tail;

    return chain;
}


AnswerSeq * createSeq(int * seq){
    AnswerSeq * ans_seq = (AnswerSeq *) malloc(sizeof(AnswerSeq));
    if (NULL == ans_seq)
        exit(-1);
    
    int ans_length = 0;
    while (-1 != *(seq+ans_length))
        ans_length ++;

    // * +1 是为了第一位给长度
    int * processed_seq = (int *) malloc(sizeof(int) * (ans_length + 1));
    if (NULL == processed_seq)
        exit(-1);

    *(processed_seq + 0) = ans_length + 1;
    for (int i=1; i<ans_length+1; i++)
        *(processed_seq + i) = *(seq +i -1);

    ans_seq->seq = processed_seq;
    return ans_seq;
}

AnswerChain * appendSeq(AnswerChain * chain, AnswerSeq * seq){
    seq->next = chain->temp->next;
    chain->temp->next = seq;
    chain->temp = seq;
    chain->answer_num += 1;
    return chain;
}